﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DP_Coins : MonoBehaviour {


    /// <summary>
    /// 现有硬币类型
    /// </summary>
    private int[] coins = new int[] { 1, 3, 5 };

    private int[] mins;

    public int CalculateNum;

	void Start () {
        CalculateMin(CalculateNum);
	}
	
	// Update is called once per frame
	void Update () {
		
	}

    private int CalculateMin(int num)
    {
        int length = num + 1;
        mins = new int[length];
        mins[0] = 0;
        for(int i = 1; i < length; i++)
        {
            mins[i] = int.MaxValue;
        }
        for (int i=0; i < length; i++)
        {
            for(int j=0; j < coins.Length; j++)
            {
                if(i>=coins[j] && mins[i] > mins[i - coins[j]])
                {
                    mins[i] = mins[i - coins[j] ]+ 1;
                }
            }
        }

        for(int i = 0; i < length; i++)
        {
            Debug.Log("金钱：" + i + "最小由 " + mins[i] + "个硬币构成");
        }

        return mins[num-1];
    }
}
